#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    int magicalString(int n) {
        if(n < 4) {
            return 1;
        }

        vector<int> s(2 * n, 0);
        s[0] = 1;
        s[1] = s[2] = 2;
        int res = 1;
        for(int i = 2, j = 3; i < n; i++) {
            if(s[i] == 1) {
                res += 1;
                s[j++] = s[j - 1] == 1 ? 2:1;
            } else {
                s[j++] = s[j++] = s[j - 1] == 1 ? 2:1;
            }
        }

        return res;
    }
};
